package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class generateParenthesis {
    public static void main(String[] args) {
        int n = 2;
        System.out.println(new generateParenthesis().generateParenthesis(n));
    }
    List<String> result = new ArrayList<>();
    String path = "(";
    String left = "(";
    String right = ")";
    public List<String> generateParenthesis(int n) {
        backTracking(n,1,0);
        return result;
    }
    public void backTracking(int n,int l_length,int r_length){
        if(l_length - r_length < 0 || l_length > n){
            return;
        }
        if(l_length == n && r_length == n){
            if(isValid(path)){
                result.add(path);
                return;
            }
        }
        for (int i = 0; i <= 1 ; i++) {
            if(i == 0){
                path += left;
                backTracking(n,l_length + 1,r_length);
                path = path.substring(0,path.length() - 1);
            }else {
                path += right;
                backTracking(n,l_length ,r_length + 1);
                path = path.substring(0,path.length() - 1);
            }
        }
    }
    public boolean isValid(String path){
       int balance = 0;
        for (int i = 0; i < path.length(); i++) {
            if(path.charAt(i) == '('){
                balance++;
            }
            else {
                balance--;
            }
            if(balance < 0){
                return false;
            }
        }
        return true;
    }
}
